/**
 * @author qiao / https://github.com/qiao
 * @fileoverview This is a convex hull generator using the incremental method.
 * The complexity is O(n^2) where n is the number of vertices.
 * O(nlogn) algorithms do exist, but they are much more complicated.
 *
 * Benchmark:
 *
 *  Platform: CPU: P7350 @2.00GHz Engine: V8
 *
 *  Num Vertices    Time(ms)
 *
 *     10           1
 *     20           3
 *     30           19
 *     40           48
 *     50           107
 */

THREE.ConvexGeometry = function( vertices ) {

    THREE.Geometry.call( this );

    var faces = [ [ 0, 1, 2 ], [ 0, 2, 1 ] ];

    for ( var i = 3; i < vertices.length; i++ ) {

        addPoint( i );

    }


    function addPoint( vertexId ) {

        var vertex = vertices[ vertexId ].clone();

        var mag = vertex.length();
        vertex.x += mag * randomOffset();
        vertex.y += mag * randomOffset();
        vertex.z += mag * randomOffset();

        var hole = [];

        for ( var f = 0; f < faces.length; ) {

            var face = faces[ f ];

            // for each face, if the vertex can see it,
            // then we try to add the face's edges into the hole.
            if ( visible( face, vertex ) ) {

                for ( var e = 0; e < 3; e++ ) {

                    var edge = [ face[ e ], face[ ( e + 1 ) % 3 ] ];
                    var boundary = true;

                    // remove duplicated edges.
                    for ( var h = 0; h < hole.length; h++ ) {

                        if ( equalEdge( hole[ h ], edge ) ) {

                            hole[ h ] = hole[ hole.length - 1 ];
                            hole.pop();
                            boundary = false;
                            break;

                        }

                    }

                    if ( boundary ) {

                        hole.push( edge );

                    }

                }

                // remove faces[ f ]
                faces[ f ] = faces[ faces.length - 1 ];
                faces.pop();

            } else { // not visible

                f++;

            }
        }

        // construct the new faces formed by the edges of the hole and the vertex
        for ( var h = 0; h < hole.length; h++ ) {

            faces.push( [
                hole[ h ][ 0 ],
                hole[ h ][ 1 ],
                vertexId
            ] );

        }
    }

    /**
     * Whether the face is visible from the vertex
     */
    function visible( face, vertex ) {

        var va = vertices[ face[ 0 ] ];
        var vb = vertices[ face[ 1 ] ];
        var vc = vertices[ face[ 2 ] ];

        var n = normal( va, vb, vc );

        // distance from face to origin
        var dist = n.dot( va );

        return n.dot( vertex ) >= dist;

    }

    /**
     * Face normal
     */
    function normal( va, vb, vc ) {

        var cb = new THREE.Vector3();
        var ab = new THREE.Vector3();

        cb.subVectors( vc, vb );
        ab.subVectors( va, vb );
        cb.cross( ab );

        cb.normalize();

        return cb;

    }

    /**
     * Detect whether two edges are equal.
     * Note that when constructing the convex hull, two same edges can only
     * be of the negative direction.
     */
    function equalEdge( ea, eb ) {

        return ea[ 0 ] === eb[ 1 ] && ea[ 1 ] === eb[ 0 ];

    }

    /**
     * Create a random offset between -1e-6 and 1e-6.
     */
    function randomOffset() {

        return ( Math.random() - 0.5 ) * 2 * 1e-6;

    }


    /**
     * XXX: Not sure if this is the correct approach. Need someone to review.
     */
    function vertexUv( vertex ) {

        var mag = vertex.length();
        return new THREE.Vector2( vertex.x / mag, vertex.y / mag );

    }

    // Push vertices into `this.vertices`, skipping those inside the hull
    var id = 0;
    var newId = new Array( vertices.length ); // map from old vertex id to new id

    for ( var i = 0; i < faces.length; i++ ) {

         var face = faces[ i ];

         for ( var j = 0; j < 3; j++ ) {

                if ( newId[ face[ j ] ] === undefined ) {

                        newId[ face[ j ] ] = id++;
                        this.vertices.push( vertices[ face[ j ] ] );

                }

                face[ j ] = newId[ face[ j ] ];

         }

    }

    // Convert faces into instances of THREE.Face3
    for ( var i = 0; i < faces.length; i++ ) {

        this.faces.push( new THREE.Face3(
                faces[ i ][ 0 ],
                faces[ i ][ 1 ],
                faces[ i ][ 2 ]
        ) );

    }

    // Compute UVs
    for ( var i = 0; i < this.faces.length; i++ ) {

        var face = this.faces[ i ];

        this.faceVertexUvs[ 0 ].push( [
            vertexUv( this.vertices[ face.a ] ),
            vertexUv( this.vertices[ face.b ] ),
            vertexUv( this.vertices[ face.c ])
        ] );

    }


    this.computeCentroids();
    this.computeFaceNormals();
    this.computeVertexNormals();

};

THREE.ConvexGeometry.prototype = Object.create( THREE.Geometry.prototype );
